package com.kehao.newcoder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class NC14Solution {

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(pRoot!=null)stack.add(pRoot);
        boolean direction = true;
        while (!stack.isEmpty()){
            Stack<TreeNode> nextStack = new Stack<>();
            ArrayList<Integer> list = new ArrayList<>();
            result.add(list);
            while (!stack.isEmpty()){
                TreeNode pop = stack.pop();
                list.add(pop.val);
                if(direction){
                    if(pop.left!=null)nextStack.push(pop.left);
                    if(pop.right!=null)nextStack.push(pop.right);
                }else {
                    if(pop.right!=null)nextStack.push(pop.right);
                    if(pop.left!=null)nextStack.push(pop.left);
                }
            }
            stack = nextStack;
            direction = !direction;
        }
        return result;
    }
}
